package com.jxb.first;

import java.util.Collections;
import java.util.LinkedList;
import java.util.Stack;

/**
 * 输入：s = "3[a]2[bc]"
 * 输出："aaabcbc"
 */
public class DecodeString_394_UseStack {

    public static void main(String[] args) {
        String s = "100[leetcode]";
        String s1 = decodeStringList(s);
        System.out.println(s1);
    }

    //用栈-定义2个栈
    //一个是存储上次追加的数据
    //一次是存储数字
    //定义每次处理字符串解码的变量，下一次解码时置为""
    public static String decodeStringStack(String s) {
        //返回结果
        String res = "";
        Stack<Integer> intStack = new Stack<>();
        Stack<String> resStack = new Stack<>();
        int idx = 0;
        while (idx < s.length()) {
            char c = s.charAt(idx);
            //处理数字
            if (Character.isDigit(c)) {
                String s1 = String.valueOf(c);
                intStack.push(Integer.valueOf(s1));
                idx++;
            }
            //处理左括号
            else if (c == '[') {
                resStack.push(res);
                res = "";
                idx++;
            }
            //处理右括号
            else if (c == ']') {
                StringBuilder temp = new StringBuilder(resStack.pop());
                Integer pop = intStack.pop();
                for (int i = 0; i< pop; i++) {
                    temp.append(res);
                }
                res = temp.toString();
                idx++;
            }
            //处理普通字符
            else {
                res += s.charAt(idx++);
            }
        }
        return res;
    }

    static int idx;

    //链表
    public static String decodeStringList(String s) {
        LinkedList<String> resLink = new LinkedList<>();
        while (idx < s.length()) {
            char c = s.charAt(idx);
            //处理数字
            if (Character.isDigit(c)) {
                /*处理数字，使数字完整*/
                String digits = getDigits(s);
                resLink.addLast(digits);
            }else if (Character.isLetter(c) || c == '[') {
                //处理普通字符和“[”
                resLink.addLast(String.valueOf(s.charAt(idx++)));
            }else {
                idx++;
                LinkedList<String> sub = new LinkedList<String>();
                //遇见了']'字符
                while (!"[".equals(resLink.peekLast())) {
                    sub.addLast(resLink.removeLast());
                }
                Collections.reverse(sub);

                //获取对应的次数
                resLink.removeLast();
                int repTime = Integer.parseInt(resLink.removeLast());
                StringBuffer t = new StringBuffer();
                String o = getString(sub);
                //构造字符串
                while (repTime-- > 0) {
                    t.append(o);
                }

                if (resLink.peekLast() != null ) {
                    resLink.addLast(resLink.removeLast() + t);
                }else {
                    resLink.addLast(t.toString());
                }

            }
        }
        return getString(resLink);
    }

    private static String getDigits(String s) {
        StringBuffer ret = new StringBuffer();
        while (Character.isDigit(s.charAt(idx))) {
            ret.append(s.charAt(idx++));
        }
        return ret.toString();
    }

    public static String getString(LinkedList<String> v) {
        StringBuffer ret = new StringBuffer();
        for (String s : v) {
            ret.append(s);
        }
        return ret.toString();
    }

}
